package main

import "fmt"

//#link: https://leetcode-cn.com/problems/chuan-di-xin-xi/
func main() {
	n, k := 5, 3
	relation := [][]int{{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}}
	fmt.Println(numWays(n, relation, k))
}

/**
* @Description: 利用动态规划 dp[i][j]表示 第i轮到达j的方案 ,dp[0][0]=1
 状态转移方程为: dp[i+1][dest]=dp[i][src] 表示可以到达的所有方案
*/
func numWays(n int, relation [][]int, k int) int {
	dp := make([][]int, k+1)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	dp[0][0] = 1
	for i := 0; i < k; i++ {
		for _, r := range relation {
			src, dest := r[0], r[1]
			dp[i+1][dest] += dp[i][src]
		}
	}
	return dp[k][n-1]
}
